﻿using Kw.Combinatorics;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Kw.Combinatorics.Bench
{
    class BinCoBench01
    {
        //
        // Alternate to Combination.BinomialCoefficient.
        //
        // Advantage:    Greater range before overflow
        // Disadvantage: 50% Slower for N-Queens
        //
        static public long BinomialCoefficient2 (int n, int k)
        {
            if (k < 0 || k > n)
                return 0;

            if (k > n - k)
                k = n - k;

            int k2 = n - k;
            long bc = 1;
            for (int ki = 1; ki <= k; ++ki)
            {
                int factor = k2 + ki;
                bc = checked (bc * factor) / ki;
            }
            return bc;
        }


        static void Main ()
        {
            int reps = 10000;
            int nMax = 38;
            long result1, result2;

            // Test for consistency between methods
            for (int n = 0; n < 38; ++n)
                for (int k = 0; k < n; ++k)
                {
                    result1 = Combination.BinomialCoefficient (n, k);
                    result2 = BinomialCoefficient2 (n, k);
                    if (result1 != result2)
                        Console.WriteLine ("Conflict at n={0}, k={1}", n, k);
                }

            var watch1 = new Stopwatch ();
            watch1.Start ();
            for (int r = 0; r < reps; ++r)
                for (int n = 0; n < nMax; ++n)
                {
                    int kMax = n;
                    for (int k = 0; k < kMax; ++k)
                        result1 = Combination.BinomialCoefficient (n, k);
                }
            watch1.Stop ();

            var watch2 = new Stopwatch ();
            watch2.Start ();
            for (int r = 0; r < reps; ++r)
                for (int n = 0; n < nMax; ++n)
                {
                    int kMax = n;
                    for (int k = 0; k < kMax; ++k)
                        result2 = BinomialCoefficient2 (n, k);
                }
            watch2.Stop ();

            Console.WriteLine ("Watch1 = {0}ms", watch1.ElapsedMilliseconds);
            Console.WriteLine ("Watch2 = {0}ms", watch2.ElapsedMilliseconds);
        }
    }
}
